class Solution
{
public:
    int maxAbsoluteSum(vector<int> &nums)
    {
        int n = nums.size();
        vector<vector<int>> dp(2, vector<int>(n));
        dp[0][0] = dp[1][0] = nums[0]; // 只与上一个状态有关，空间可以优化掉
        int maxSum = abs(nums[0]);
        for (int i = 1; i < n; ++i)
        {
            dp[0][i] = min(dp[0][i - 1] + nums[i], nums[i]);
            dp[1][i] = max(dp[1][i - 1] + nums[i], nums[i]);
            maxSum = max(maxSum, abs(dp[0][i]));
            maxSum = max(maxSum, abs(dp[1][i]));
        }
        return maxSum;
    }
};